package com.sortingalgorithm;

import java.util.Arrays;

public class MergeSort2 {
    public static void main(String[] args) {
        int []arr = {9,8,7,6,5,4,3,2,1};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int [] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        int start = 0;
        int end = arr.length - 1;
        int[] copy = new int[end + 1];

    }

    // 排序和归并
    private static void sort(int[] arr,int [] copy,int start,int end){
        if(start < end){
            int mid = start +((end - start) >> 1);
            // 左边有序
            sort(arr,copy,start,mid);
            // 右边有序
            sort(arr,copy,mid + 1,end);
            // 左右有序数组合并
            merge(arr,copy,start,mid,end);
        }
    }

    private static void merge(int [] arr,int [] copy,int start,int mid,int end){
        int i = mid;
        int j = end;
        int s = end;
        while (i >= start && j > mid){
            if(arr[i] > arr[j]){
                copy[s --] = copy[i -- ];
            }else{
                copy[s --] = copy[j -- ];
            }
        }

        while (i >= start){
            copy[s --] = copy[i--];
        }
        while (j >= mid){
            copy[s --] = copy[j--];
        }

        for(int k = s;k <= end;k++){
            arr[k]  = copy[k];
        }
    }




}
